//
// Created by Incredible on 17/3/16.
//

#ifndef MERGESORT_INSERTIONSORT_H
#define MERGESORT_INSERTIONSORT_H

#include <iostream>

using namespace std;

/**
 * 插入排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; ++i) {

        //每次内层循环找到应该arr[j]的位置
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {

            swap(arr[j], arr[j - 1]);
        }
    }
}

/**
 * 插入排序,改进版，利用一个单位空间，将一次交换替换为一次赋值
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSortBeat(T arr[], int n) {
    for (int i = 1; i < n; i++) {

        //寻找arr[i]的插入位置
        T nux = arr[i];
        int j;      //保存arr[i]应该的插入位置
        for (j = i; j > 0 && arr[j - 1] > nux; j--) {

            arr[j] = arr[j - 1];
        }
        //将nux 放入其应该存在的位置
        arr[j] = nux;
    }
}

/**
 * 插入排序,改进版，利用一个单位空间，将一次交换替换为一次赋值.
 * 用途：排序数组部分区间
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSortBeat(T arr[], int l, int r) {
    for (int i = l+1; i <= r; i++) {

        //寻找arr[i]的插入位置
        T nux = arr[i];
        int j;      //保存arr[i]应该的插入位置
        for (j = i; j > l && arr[j - 1] > nux; j--) {

            arr[j] = arr[j - 1];
        }
        //将nux 放入其应该存在的位置
        arr[j] = nux;
    }
}

#endif //HEAPSORT_INSERTIONSORT_H
